A computing device that performs cryptographic signatures and/or decryptions using the private key of a public key pair, and that stores the private key locally on stable storage, is typically vulnerable to exposure of that private key if the device is captured. While encryption of the private key under a password is common, the ease with which passwords succumb to offline dictionary attacks implies that better protections are needed. Many such protections have been proposed, but most require tamper-resistance of the device. Others used in practice replace the password with a stronger key stored on another device that the user holds, thus moving the burden of protection to that device. Some of these existing approaches will now be discussed.
One existing approach proposes methods to encrypt a DSA (Digital Signature Algorithm) or RSA (Rivest-Shamir-Adleman) private key using a password so that guesses at the password cannot be verified by an attacker who captures the device holding that private key, see, e.g., D. N. Hoover et al., “Software Smart Cards via Cryptographic Camouflage,” 1999 IEEE Symposium on Security and Privacy, pp. 208–215,May 1999, the disclosure of which is incorporated by reference herein. However, this feature comes at a severe price. For example, the device's public key must be kept secret, even from the device itself. Obviously, this is because when the attacker learns the public key, he can then verify a successfully decrypted private key. So, the public key must be hidden from all but a few trusted servers that verify signatures produced by the device or encrypt messages for the device. Also, with this approach, it is essential that no verifiable plaintext be encrypted, since this, too, could be used to verify guesses at the password. However, these are awkward constraints to be imposed on a cryptographic system.
Another existing approach proposes simply not storing the device's private key on the device, but rather having the device download the private key from the server when needed, see, e.g., R. Perlman et al., “Secure Password-based Protocol for Downloading a Private Key,” Proceedings of the 1999 Network and Distributed System Security Symposium, February 1999, the disclosure of which is incorporated by reference herein. In this approach, to ensure that the private key is downloaded only to the user's device, the device first proves it has been given the user's password. For this purpose there are numerous published protocols by which the device can authenticate to and exchange a key with a server using a password input by its user, without exposing that password to offline dictionary attacks.
Some of these protocols require the device to already have a public key for the server, see, e.g., T. M. A. Lomas et al., “Reducing Risks from Poorly Chosen Keys,” ACM Operating Systems Review, 23(5):14–18, December 1989; S. Halevi et al., “Public-key Cryptography and Password Protocols,” ACM Conference on Computer and Communications Security, pp. 122–131, 1998; W. Fordet al., “Server-assisted Generation of a Strong Secret from a Password,” IEEE International Workshop on Enterprise Security, 2000, the disclosures of which are incorporated by reference herein.
Some of these protocols do not require the device to already have a public key for the server, see, e.g., S. M. Bellovin et al., “Encrypted Key Exchange: Password-based Protocols Secure Against Dictionary Attacks,” 1992 IEEE Symposium on Security and Privacy, pp. 72–84, 1992; D. Jablon, “Strong Password-only Authenticated Key Exchange,” ACM Computer Communication Review 26(5):5–20, 1996, T. Wu, “The Secure Remote Password Protocol,” 1998 Network and Distributed System Security Symposium, February 1999; M. Bellare et al., “Authenticated Key Exchange Secure Against Dictionary Attacks,” Advances in Cryptology—EUROCRYPT 2000, Lecture Notes in Computer Science 1807, pp. 139–155, 2000; V. Boyko et al., “Provably Secure Password Authentication and Key Exchange Using Diffie-Hellman,” Advances in Cryptology—EUROCRYPT 2000, Lecture Notes in Computer Science 1807, pp. 156–171, 2000; and P. MacKenzie et al., “Password Authenticated Key Exchange Based on RSA,” Advances in Cryptology—ASIACRYPT 2000, pp. 599–613, 2000, the disclosures of which are incorporated by reference herein.
Since the device stores at most only public information, its capture is of no consequence. On the other hand, in all of these protocols, the server either knows the user's password or else can mount an offline dictionary attack against it.
More importantly, when these protocols are used for the retrieval of a private key from the server, the private key (which would most likely be encrypted with the password) would be exposed to the server after a successful offline dictionary attack on the password.
Other existing approaches resort to multiple servers and require that, at most, some threshold number of these servers cooperate in a dictionary attack, see, e.g., the above-referenced W. Ford et al. approach. But this means that some server must be trusted. Also, such existing approaches do not address the possibility that an attacker already knows the user's password or guesses it quickly. Once the attacker guesses the password and downloads the private key, the attacker can use it for an unlimited time.
Still another existing approach to such a cryptographic security problem is to ensure that the private key cannot be used to sign messages dated before the device was captured. This is achieved by “forward secure” signature schemes, which intuitively change the private key (but not the public key) over time so that the captured private key can be used to sign messages only dated in the future, see, e.g., M. Bellare et al., “A Forward-secure Digital Signature Scheme,” Advances in Cryptology—CRYPTO '99, Lecture Notes in Computer Science 1666, pp. 431–438, 1999; and H. Krawczyk, “Simple Forward-secure Signatures From Any Signature Scheme,” ACM Conference on Computer and Communication Security, pp. 108–115, November 2000, the disclosures of which are incorporated by reference herein. However, such an approach does not prevent any future signatures by the attacker once the device is captured, but rather permits them in a limited way.
If the device can sense that its private key is about to be discovered, as might be possible if the device is a coprocessor with tamper detection circuitry, then another alternative is for the device to change the private key when it detects a pending compromise so that future signatures subliminally disclose to an authority receiving those signatures that the device has been compromised, see, e.g., J. H{dot over (a)}stad et al., “Funkspiel Schemes: An Alternative to Conventional Tamper Resistance,” ACM Conference on Computer and Communications Security, pp. 125–133, November 2000, the disclosure of which is incorporated by reference herein. However, such an approach also does not prevent any future signatures by the attacker once the device is captured, but rather permits them in a way that subliminally alerts an authority.
Yet other existing approaches employ “server aided protocols,” whereby the computational burden of a secret cryptographic computation is moved from the device to a more powerful server. Some of these protocols place trust in the server and thus expose the device's private information to the server, see, e.g., N. Asokan et al., “Server-Supported Signatures,” Journal of Computer Security 5(1), 1997; and D. Dean et al., “Cryptography as a Network Service,” 2001 ISOC Symposium on Network and Distributed System Security, February 2001, the disclosures of which are incorporated by reference herein. While others of these protocols attempt to hide the private key from the server but nevertheless have the server do the bulk of the computation, see, e.g., T. Matsumoto et al., “Speeding up Computation with Insecure Auxiliary Devices,” Advances in Cryptology—CRYPTO '88, Lecture Notes in Computer Science 403, pp. 497–506, 1989; P. Béguin et al., “Fast Server-Aided RSA Signatures Secure Against Active Attacks,” Advances in Cryptology—CRYPTO '95, Lecture Notes in Computer Science 963, pp. 57–69, 1995; and S. Hong et al., “A New Approach to Server-aided Secret Computation,” 1st International Conference on Information Security and Cryptology, pp. 33–45, 1998, the disclosures of which are incorporated by reference herein.
However, such server aided protocols attempt to reduce the computation required of the user's device rather than attempting to render the device impervious to an offline dictionary attack once captured.
Thus, there exists a need for techniques which overcome drawbacks associated with existing cryptographic approaches and which thereby make networked cryptographic devices more resilient to capture.